The present invention generally relates to scheduling events in computers and system networks and in particular to dynamically increasing the capacity of a circular timer queue.
In many computer networks, computerized telephone and billing systems, etc., there are intercommunication mechanisms in computers and other types of systems which handle multiple events, where such mechanisms are often presented with the problem of scheduling a certain event to happen at a particular time which is to be arranged for set-up in the system.
Many memory systems for example, have queues of items to be accessed or handled in a particular sequence. Many programs have lists of instructions which are sequenced also to be handled in a particular arrangement of time events. Sometimes, thousands of different items are placed in queues in order to be available for access in a particular sequence or order.
For example, in the compilation of a telephone directory or a directory of certain businesses in a certain location or a directory of the names of people associated with a certain group, these are all examples of data words or information which are placed in queues and which may be accessed, acquired and used or deleted at certain moments of time.
Additionally, once such a list is compiled, it is very often necessary to place insertions into the queue list, for example, new person""s names may be added to a group organization list, or new telephone numbers and addresses and names may be put in a telephone book. Similarly, and often in Kerberos Security Systems, a list of authenticated users and appropriate passwords and tickets may be involved in a list of such useful items.
In each and any of the cases, when it is necessary to add to a particular list, it is sometimes a rather magnitudinous task to achieve this type of event when there is required the normal situation where the system must check through each of the items in the list step-by-step until it reaches its selected position where the insertion must be made, after which a stop operation must occur, and after which the new item is inserted into the system which performs the completion of this operation. However, in so doing, sometimes thousands and thousands of entries must be sequenced through to find the exact point where the new insertion is to be made. This is very time-consuming and exceedingly complex in terms of programming the request to be inserted at a particular point in a large sequence of other requests in a list.
The normal method for this to happen is that there be a sequential scan of each item, item-by-item, step-by-step, until there is reached or achieved the proper insertion point. The performance cost of queue searching for inserting events which need to be handled at some fixed time in the future, is quite an expensive proposition. However, the queues which must be scanned sequentially are used very often for these purposes because they are simple to implement and maintain, and can reflect the linear nature of the problem to be solved in finding the correct placement point or item into which the new event is to be inserted. Additionally, such a technique is inherently slow, and thus also becomes increasingly costly, as more entries are added to the queue, and considerable time latency factors are involved in the mechanism which must traverse through the queue in order to find the right new entrance point.
Likewise, the same sort of difficulties arise when an inserted transient timer entry is now desired to be deleted and removed.
Traditionally, timer events are maintained in a queue structure, and each timer event has a value associated with it. The value of the timer event determines when the event would or should happen after the previous timer event has happened.
As an example, if five events are to happen at t+3, then t+8, then t+45, then t+55, then t+56, (where xe2x80x9ctxe2x80x9d is current time), then as an example, the queue may be considered to look as follows:
TE(3)xe2x80x94TE(5)xe2x80x94TE(37)xe2x80x94TE(10)xe2x80x94TE(1)
Where xe2x80x9ctxe2x80x9d is the current time and the bracketed value (X) represents the added time, for example, in seconds, which indicates the event as occurring just after the time count that the previous event had occurred.
In this particular operation, after one tick of time has occurred (that is to say, at t+1), then the timer queue could be represented to look as follows:
TE(2)xe2x80x94TE(5)xe2x80x94TE(37)xe2x80x94TE(10)xe2x80x94TE(1)
The difference here, is that the first item has now changed from TE(3) to now be TE(2).
With this type of scheme being used, it is seen to be very time-consuming to insert a transient timer entry in the queue, since the fixed timer entries need to be scanned from the xe2x80x9cstartxe2x80x9d of the queue until the correct place is found. For example, if a temporary New Timer Entry (NTE) is to be added, for example, which is to happen after 48 ticks, then the entries of the timer queue will need to be scanned until an event is found which will happen after 48 ticks, and then the transient New Timer Entry (NTE) needs to be inserted just prior to that event. Thus, in the above example, it would be necessary to scan step-by-step for each of the entries.
Thus, in the above example, the timer queue after the new event insertion (NTE) will now appear as shown below:
TE(2)xe2x80x94TE(5)xe2x80x94TE(37)xe2x80x94NTE(4)xe2x80x94TE(6)xe2x80x94TE(1)
Thus, the New Timer Entry insertion which is NTE(4) required the scanning of four previous entries.
Now, in the situation where the queue has thousands of entries, this type of operation will be seen to be very time-consuming in order to provide for a new event insertion. Likewise later when the removal of a temporary New Timer Entry (NTE) was desired, the usual and ordinary solution was to sequence through each of the fixed timer entries until the temporary NTE was found so it could then be deleted. Here much wasteful time was consumed.
The present system involves a method for managing timer events and expanding the number of pre-existing fixed timer entries, FTEs. This does not require any scan of the existing entries in the queue, and as a result, provides for an extensive speeding-up for handling the sequence of events which are desired to be utilized in a queue. The new method uses the operation of the timer queue as if it were maintained as a circular queue. Here, the circular queue would have xe2x80x9cNxe2x80x9d permanent entries, where xe2x80x9cNxe2x80x9d is a chosen number, but an arbitrary one depending on the number of permanent entries or FTEs (fixed timer entries) that one would like to configure into the queue. Also, the number xe2x80x9cNxe2x80x9d then determines the maximum duration in timer ticks that can be handled by this type of configuration.
In the co-pending companion case, U.S. Ser. No. 09/602,692, the major focus was to provide the xe2x80x9cinsertionxe2x80x9d of a transient or temporary timer entry designated as an NTE or new timer entry.
Still, in the co-pending companion case, U.S. Ser. No. 09/602,693, the major focus was to handle the problem of removing and deleting such a new timer entry (NTE) when it is no longer needed or useful.
The method of the present invention relates to dynamically allowing a timer queue to process NTEs with duration in timer ticks greater than the limit of the previous existing timer queue, thus increasing capacity for a larger number of FTEs. This is achieved by inserting additional FTEs to the circular queue and increasing the value of xe2x80x9cNxe2x80x9d to a new xe2x80x9cNxe2x80x9d.
The system here contemplates a circular queue of xe2x80x9cNxe2x80x9d fixed timer entries (FTEs). A request to process an NTE (New Timer Entry) with a duration greater than N timer ticks is presented to the circular queue. Without the method of the present invention, the NTE could not be handled. Using the method of the present invention, however, the circular queue is expanded to a size allowing the requested duration to be handled through the dynamic insertion of new FTEs (Fixed Timer Entries).
For example, if the timer xe2x80x9ctickxe2x80x9d or xe2x80x9cperiodxe2x80x9d is 100 milliseconds, and xe2x80x9cNxe2x80x9d is 9,000, then this queue will be capable of handling any timer request within a period of 15 minutes. If a request for a duration of 20 minutes is made, the method of the present invention creates 3,000 additional FTEs in order to allow the processing of the request. This resets N to 12,000, making the queue capable of handling any timer request for a duration up to 20 minutes.
The present system provides for the utilization of a timer queue as a circular queue which has xe2x80x9cNxe2x80x9d permanent entries which are designated as Fixed Timer Entries (FTEs). The chosen number for the configuration, which is the number xe2x80x9cNxe2x80x9d, determines the maximum duration of timer requests that can be handled.
The method involves allocating xe2x80x9cNxe2x80x9d fixed timer entries (FTEs) and assigning a timer value of xe2x80x9c1xe2x80x9d to each of these timer entries. These timer entries are linked to form a circularly linked list and the addresses of these timer entries are saved in an array which is used to access the fixed elements of the queue directly.
A xe2x80x9cCurrent Timer Indexxe2x80x9d (current position in a circular Timer Queue, designated CTI) is assigned so that this is equivalent to the xe2x80x9cCurrent Time In Ticksxe2x80x9d, mod xe2x80x9cNxe2x80x9d.
In general operations, the system permits transient new timer entries (NTEs) to be inserted between two selected timer entries (TEs). This involves converting the requested duration to duration in terms of xe2x80x9ctimer ticksxe2x80x9d.
If the value of xe2x80x9ctimer ticksxe2x80x9d exceeds xe2x80x9cNxe2x80x9d, then the method of the present invention expands the circular queue by creating additional FTEs. The number of FTEs created depends on the number of timer ticks requested. For example, if N equals 10 and a request for an NTE at 15 timer ticks is made, then 5 additional FTEs are created. After creating the additional FTEs, xe2x80x9cNxe2x80x9d is set to the new number of FTEs, links are reassigned so as to preserve the circular queue, and TICK13 ADJUST is recalculated so that xe2x80x9cCurrent Timer Indexxe2x80x9d does not change.
Once the value of xe2x80x9ctimer ticksxe2x80x9d is less than or equal to xe2x80x9cNxe2x80x9d, the program will allocate a new timer entry (NTE), assign a timer value of xe2x80x9c0xe2x80x9d to this entry, then assign a handle to this entry. xe2x80x9cTimer Indexxe2x80x9d is assigned the value of (CURRENT13 TIME13 IN13 TICKS+NEW13 TIMER13 TICKS) mod xe2x80x9cNxe2x80x9d. Then, there is made an insertion of this new timer entry (NTE) prior to the timer entry which is pointed-to by the xe2x80x9cTimer Indexxe2x80x9d within the Timer Queue.
The method of the present invention is useful in a system including a timer management module for managing a circular queue having N fixed timer entries (FTEs). The program enables dynamic capacity increase of size M by extending the pointer array referencing the circular queue by M, copying the first xe2x80x9cCurrent Timer Indexxe2x80x9d entries to the extended pointer array entries, allocating M FTEs, and linking the M FTEs for addition within the circular queue. Thus, the newly arranged number of total entries (FTEs) is the sum of N+M.
In order to provide a more understandable foundation for the present invention, a brief summary of the operations for insertion (U.S. Ser. No. 09/602,692) of Fixed Timer Entries (FTEs) will be outlined so as to enable a better appreciation of the present invention which enables the expansion of a queue from a previously-set number N of FTEs to an expanded number of FTEs (N+M). FIGS. 1, 2A, 2B and 3A illustrate the environment and factors of a circular queue. FIGS. 3B, 3C and 6A and 6B summarize the insertion of a new Transient Timer Entry (NTE).
FIGS. 4A-4G and 7A-7D provide the substance of the present invention which relates to taking a circular queue of N Fixed Timer Entries and expanding this queue to N+M Fixed Timer Entries for operation in a circular queue.